package Hot_100;/*
* 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers
* */

/*
分析:
    两个 个位数相加后可能会进位
    链表是按照逆序存储： 2->4->3 对应 342

思路:
    在同一个while里遍历两个链表，所以时间复杂度为O(n)
    对两个链表同位数的个位数进行相加，注意可能出现进位
    链表的长度不一定相同，所以不够位数的要补0，直到两个链表的有效位数都遍历完
    最后要注意最高位可能需要进1
* */
public class T2_addTwoNumbers {
    public static void main(String[] args) {
//        测试 l1=[2,4,3]  l2=[5,6,4]
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(3);
        l1.next = l2;
        l2.next = l3;
        l3.next = null;

        ListNode l4 = new ListNode(5);
        ListNode l5 = new ListNode(6);
        ListNode l6 = new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        l6.next = null;

        ListNode listNode = addTwoNumbersTest2(l1, l4);
        while (listNode != null) {
            System.out.print(listNode.val);
            listNode = listNode.next;
        }
    }

    static ListNode addTwoNumbersTest1(ListNode l1, ListNode l2) {
        ListNode prev = new ListNode();
        //创建存储结果的链表 第一个结点充当头结点，为了方便链表的操作；其存储的数据没有实际意义

        int carry = 0;  //进位 0或1

        ListNode cur = prev;  //指向结果链表的指针


        while (l1 != null || l2 != null) {    //保证能遍历完l1和l2中最长的链表

            //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int x = l1 != null ? l1.val : 0;

            //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int y = l2 != null ? l2.val : 0;

            //将两个链表的值，进行相加，并加上进位数
            int sum = x + y + carry;

            //计算进位数
            carry = sum / 10;

            //计算两个数的和，此时排除超过10的请况（大于10，取余数）
            sum = sum % 10;

            //将求和数赋值给新链表的节点，
            cur.next = new ListNode(sum);

            //将新链表的节点后移
            cur = cur.next;

            //当链表l1不等于null的时候，将l1 的节点后移
            if (l1 != null) {
                l1 = l1.next;
            }

            //当链表l2 不等于null的时候，将l2的节点后移
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        //如果最后两个数，相加的时候有进位数的时候，就将进位数，赋予链表的新节点。
        if (carry == 1) {
            cur.next = new ListNode(carry);
//            cur = new Hot_100.ListNode(carry);
        }

        //返回链表的首节点
        return prev.next;
    }

    static ListNode addTwoNumbersTest2(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode();
        ListNode cur=pre;
        int carry=0,sum;

        while (l1 != null || l2 != null) {
            int t1 = l1==null?0:l1.val;
            int t2 = l2==null?0:l2.val;

            sum=t1+t2+carry;
            carry=sum/10;       //进位
            sum%=10;            //该位的实际数值

            if (l1 != null) {
                l1=l1.next;
            }

            if (l2 != null) {
                l2=l2.next;
            }

            cur.next = new ListNode(sum);
            cur=cur.next;
        }

        if(carry==1){
            cur.next=new ListNode(1);
        }

        return pre.next;
    }
}


// 链表
class ListNode {
    int val;        //默认值为0
    ListNode next;  //默认值为null
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}